//
// 
// 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连
//。 
//
// 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 
//
// 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 
//isConnected[i][j] = 0 表示二者不直接相连。 
//
// 返回矩阵中 省份 的数量。 
//
// 
//
// 示例 1： 
//
// 
//输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 200 
// n == isConnected.length 
// n == isConnected[i].length 
// isConnected[i][j] 为 1 或 0 
// isConnected[i][i] == 1 
// isConnected[i][j] == isConnected[j][i] 
// 
// 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 
// 👍 664 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class NumberOfProvinces {
    public static void main(String[] args) {
        int[][] isConnected = {{1,1,0},{1,1,0},{0,0,1}};
        new NumberOfProvinces().new Solution().findCircleNum(isConnected);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 我这个dfs为何如此的拉跨，还是找的入口
         * 1.找到入口之后将两个城市的关系先清了
         * 2.遍历当前节点找到所有的连接城市，将新的城市传入dfs进行遍历
         * 3.返回找到的入口个数就行了
         * 深度优先遍历可以使用一个visited数组来保存访问状态
         * 我是对之前的数组进行了修改，最好还是用visited来判断好一些
         */
        public int findCircleNum(int[][] isConnected) {
            int n = isConnected.length;
            int res = 0;
            boolean[] visited = new boolean[n];
            for (int i = 0; i < n ; i++) {
                if (!visited[i]) {
                    res++;
                    dfs(i, isConnected, visited);
                }
            }
            return res;
        }
        public void dfs (int index, int[][] isConnected, boolean[] visited){
            visited[index] = true;//这样访问很简洁
            for (int i = 0; i < isConnected.length ; i++) {
                if (isConnected[index][i] == 1 && !visited[i]) {
                    dfs(i, isConnected,visited);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    /**
     * 使用并查集的方式解决问题
     * 并（Union）：合并
     * 查（Find）：查找
     * 集（Set）：使用的数据结构，便于查找集合中的元素
     */
    class UnionFind{
        //子节点为key，父节点为value
        public Map<Integer,Integer> father;//储存所有的父节点
        public int count;//统计所有父节点的个数，最终结果
        public UnionFind(){//初始化
            father = new HashMap<>();
            count = 0;
        }

        /**
         * 添加父节点的方法（树根）
         */
        public void add(Integer i){
            if (!father.containsKey(i)){
                father.put(i, null);
                count++;
            }
        }

        /**
         * 合并两个帮派，随便和到哪边都行啊，大家都是兄弟
         * 合并完之后记得总数--
         */
        public void merge(Integer x, Integer y){
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot!=yRoot){
                father.put(yRoot, xRoot);
                count--;
            }
        }

        /**
         * 查找并进行树的压缩
         */
        public Integer find(Integer x){
            int root = x;

            while (father.get(root)!=null){
                root = father.get(root);//循环找到根为止
            }

            //这里还需要进行一个数据压缩，让树的高度为2
            while (x!=root){
                int originFather = father.get(x);
                father.put(originFather, root);
                x = originFather;
            }

            return root;
        }

        public int findCircleNum(int[][] isConnected) {
            UnionFind uf = new UnionFind();
            for (int i = 0; i < isConnected.length ; i++) {
                uf.add(i);
                //这样是避免前后重复添加，因为只需要添加一半
                for (int j = 0; j < i; j++) {
                    if (isConnected[i][j]==1) {
                        uf.merge(i, j);
                    }
                }
            }
            return uf.count;
        }

    }

}









































